This invention relates generally to a material control system in a network-like, vehicle-based, material handling system and in particular to a method for determining a node based penalty for use in a path finding algorithm for an automated material handling system (AMHS).
Electrically powered motor transport vehicles (MTVs) are used in manufacturing and warehouse environments for transporting and manipulating articles of manufacture. Such vehicles are desirable in these environments due to their clean operation and low noise. Often, such vehicles are propelled along a fixed rail or track, allowing precise control of movement along a predetermined path.
In particular, computer controlled materials transport systems are known for moving materials, such as semiconductor wafers, among various workstations of a semiconductor fabrication facility. In such a wafer transport system, a monorail track is routed past the work stations and a plurality of electric vehicles are mounted on the track and moveable thereon for delivering wafers to successive work stations and for removing wafers therefrom after requisite processing operations have been accomplished. The track is composed of interconnected track sections that usually include one or more routing sections or modules that are operative to provide plural paths along the track. In general, a node is a location where a vehicle is stopped, loaded, unloaded, or redirected. Thus, a node can be a workstation that a vehicle must pass through or an intersection of one or more tracks where the vehicle may be redirected.
The vehicles on the track typically operate in a connected mode in which a central controller, usually a computer, assigns destinations to vehicles and monitors the operation of the entire material handling system. This monitoring may include monitoring the status and location of each MTV, the status and location of material lots needed to be transported, and the status of each node of the material transport system.
The central controller is therefore responsible for the execution of move requests to transport a material lot from a source node to a destination node. In addition, the central controller is also responsible for the overall efficiency of the material transport system. For example, the more efficient use of the MTVs results in needing fewer of them, which reduces the cost of the overall system. In addition, by selecting routes to avoid “traffic jams” at busy nodes, the central controller may avoid a number of MTVs waiting in a queue for a pick-up or a delivery of a material lot. While waiting in a queue, the MTV is being used inefficiently and the material transport system will experience longer delivery times.
In selecting a route, the central controller use an algorithm that not only takes into account the distance between the source and destination nodes, but also takes into account the block time at the intermediate nodes. Typically, the penalty block time at the various nodes is a predetermined linear-time-invariant penalty that is merely a constant multiplied by the number of MTVs in the input queue. However, an important consideration in semiconductor fabrication facilities is the quick transition of material between the source and the destination. Vehicles tend to cluster around busy nodes at certain production times because of lot batching and frequent move requests at one specific node. Semiconductor manufacturing is by nature a stochastic process and linear-time-invariant node penalties are not flexible enough to allow the proper optimized route setting. In particular, linear-time-invariant node penalties are adequate for AMHS systems that experience insignificant congestion. However, these penalties are inadequate for systems that experience heavy congestion, and in particular systems that experience heavy congestion aggravated by an AMHS layout that is not flexible enough to handle a large number of moves in the same area within a short period of time.
What is needed, therefore, is a routing algorithm that will allow an AMHS or MTC to select an optimum route on the basis of dynamic node penalties.